﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Netcached.Hash
{
    class KetamaHashing : IConsistentHashing
    {
        int numberOfHashesPerServer = 200;
        Dictionary<uint, string> serverMap;
        uint[] keyContinuum;

        public KetamaHashing(string[] serverAddresses)
        {
            Setup(serverAddresses);
        }

        private void Setup(string[] serverAddresses)
        {
            serverMap = new Dictionary<uint, string>();
            keyContinuum = new uint[numberOfHashesPerServer * serverAddresses.Length];

            for (int serverIdx = 0; serverIdx < serverAddresses.Length; serverIdx++)
            {
                string server = serverAddresses[serverIdx];
                for (int i = 0; i < numberOfHashesPerServer; i++)
                {
                    uint hash = HashAlgorithm.HashFNV1a32bits(Encoding.ASCII.GetBytes(server + i));
                    serverMap.Add(hash, server);
                    keyContinuum[serverIdx * i] = hash;
                }
            }

            Array.Sort(keyContinuum);
        }

        public string GetServerAddress(string objectKey)
        {
            uint objectKeyHash = HashAlgorithm.HashFNV1a32bits(Encoding.ASCII.GetBytes(objectKey));
            
            int serverKeyIndex = BinarySearch(keyContinuum, objectKeyHash, 0, keyContinuum.Length);
            uint serverKeyValue = keyContinuum[serverKeyIndex];

            return serverMap[serverKeyValue];
        }

        int BinarySearch(uint[] array, uint key, int min, int max)
        {
            int returnValue = -1;

            if (array[array.Length - 1] < key)
            {
                returnValue = array.Length - 1;
            }
            else
            {
                while (true)
                {
                    int mid = (min + max) / 2;

                    if (array[mid] > key && array[mid - 1] <= key)
                    {
                        returnValue = mid;
                        break;
                    }
                    else if (array[mid] < key)
                    {
                        min = mid + 1;
                    }
                    else if (array[mid] > key)
                    {
                        max = mid - 1;
                    }
                }
            }

            return returnValue;
        }
    }
}
